package com.wdc.avltree;

public class AVLTree {
    static class AVLNode{
        int key;
        Object value;
        int height = 1;
        AVLNode left;
        AVLNode right;

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 获取当前结点的高度
     * @param node
     * @return
     */
    private int getHeight(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    /**
     * 更新结点的高度
     * @param node
     */
    private void updateHeight(AVLNode node){
        node.height = Math.max(getHeight(node.left),getHeight(node.right))+1;
    }


    /**
     * 判断当前结点的左右子节点的高度是否满足要旋转
     * @param node
     */
    private int bf(AVLNode node){
        int c = getHeight(node.left) - getHeight(node.right) ;
            //说明高度差小于 1 不用旋转
            //说明左边高
            // 说明右边高
        return getHeight(node.left) - getHeight(node.right);
    }



}
